package problem740;

//740.删除并获得点数
// https://leetcode.cn/problems/delete-and-earn/description/

class Solution {
    public int deleteAndEarn(int[] nums) {
        //转化为打家劫舍问题1
        int n = 20002;
        int[] hash = new int[n];
        for(int x: nums) {
            hash[x] += x;
        }
        int[] f = new int[n];
        int[] g = new int[n];
        g[0] = hash[0];
        for(int i = 1; i<n; i++) {
            f[i] = Math.max(g[i-1], f[i-1]);
            g[i] = f[i-1] + hash[i];
        }
        return Math.max(f[n-1], g[n-1]);
    }
}

/*
rob1 为打家劫舍1 的代码思路:
g[i]: 到第i个房子并且拿第i个房间现金的最大金额
g[i] = f[i-1] + nums[i];
f[i]: 到第i个房子并且不拿第i个房间现金的最大金额
f[i] = Math.max(g[i-1], f[i-1]);
*/